import java.util.*;

public class BinaryTree {
    static class TreeNode{
        public char val;//值域
        public TreeNode left;//左孩子
        public TreeNode right;//右孩子

        public TreeNode(char val) {
            this.val = val;
        }
    }
    public TreeNode root;//将来这个引用指向根节点
    //创建一棵二叉树
    public TreeNode creatTree(){
        TreeNode A = new TreeNode('A');
        TreeNode B= new TreeNode('B');
        TreeNode C = new TreeNode('C');
        TreeNode D = new TreeNode('D');
        TreeNode E = new TreeNode('E');
        TreeNode F = new TreeNode('F');
        TreeNode G = new TreeNode('G');
        TreeNode H = new TreeNode('H');
        A.left = B;
        A.right = C;
        B.left = D;
        B.right = E;
        C.left = F;
        C.right = G;
        E.right = H;
        return A;
    }
    //前序遍历
    public void preOrder(TreeNode root){
        if(root == null) return;
        System.out.print(root.val + " ");
        preOrder(root.left);
        preOrder(root.right);
    }

    //将前序遍历的结果存储到List中
    //这个方法没有有效利用返回值
   // List<TreeNode> list = new ArrayList<>();
   /* public List<TreeNode> preOrder2(TreeNode root){
        if(root == null) return list;
        list.add(root);
        preOrder2(root.left);
        preOrder2(root.right);
        return list;
    }*/
    public List<Character> preOrder3(TreeNode root){
        List<Character> ret = new ArrayList<>();
        if(root == null) return ret;
        ret.add(root.val);
        List<Character> leftTree = preOrder3(root.left);
        ret.addAll(leftTree);
        List<Character> rightTree = preOrder3(root.right);
        ret.addAll(rightTree);
        return ret;
    }
    public List<Character> preorderTraversal(TreeNode root) {
        List<Character> list = new ArrayList();
        if(root == null) return list;
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
        TreeNode top = null;
        while(cur != null || !stack.isEmpty()){
            while(cur != null){
                stack.push(cur);
                list.add(cur.val);
                cur = cur.left;
            }
            top = stack.pop();
            cur = top.right;
        }
        return list;
    }

    public List<TreeNode> preOrder2(TreeNode root){
        List<TreeNode> ret = new ArrayList<>();
        if(root == null) return ret;
        ret.add(root);
        List<TreeNode> leftTree = preOrder2(root.left);
        ret.addAll(leftTree);
        List<TreeNode> rightTree = preOrder2(root.right);
        ret.addAll(rightTree);
        return ret;
    }
    //中序遍历
    public void inOrder(TreeNode root){
        if(root == null) return;
        inOrder(root.left);
        System.out.print(root.val + " ");
        inOrder(root.right);
    }
    //中序遍历（使用顺序表）
    public List<Character> inorderTraversal(TreeNode root) {
        List<Character> ret = new ArrayList();
        if(root == null) return ret;
        List<Character> leftTree =  inorderTraversal(root.left);
        ret.addAll(leftTree);
        ret.add(root.val);
        List<Character> rightTree =  inorderTraversal(root.right);
        ret.addAll(rightTree);
        return ret;
    }
    //使用循环遍历
    public List<Character> inorderTraversal1(TreeNode root) {
        List<Character> list = new ArrayList();
        if(root == null) return list;
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
        TreeNode top = null;
        while(cur != null || !stack.isEmpty()){
            while(cur != null){
                stack.push(cur);
                cur = cur.left;
            }
            top = stack.pop();
            list.add(top.val);
            cur = top.right;
        }
        return list;
    }
    //后序遍历
    public void postOrder(TreeNode root){
        if(root == null) return;
        postOrder(root.left);
        postOrder(root.right);
        System.out.print(root.val + " ");
    }
    //后序遍历存储的是值
    public List<Character> postorderTraversal(TreeNode root) {
        List<Character> ret = new ArrayList();
        if(root == null) return ret;
        List<Character> leftTree = postorderTraversal(root.left);
        ret.addAll(leftTree);
        List<Character> rightTree = postorderTraversal(root.right);
        ret.addAll(rightTree);
        ret.add(root.val);
        return ret;
    }
    //使用循环遍历
    public List<Character> postorderTraversal1(TreeNode root) {
        List<Character> list = new ArrayList();
        if (root == null) return list;
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
        TreeNode top = null;
        TreeNode prev = null;
        while (cur != null || !stack.isEmpty()) {
            while (cur != null) {
                stack.push(cur);
                cur = cur.left;
            }
            //因为是左右根要防止右边还有元素
            top = stack.peek();
            if (top.right == null || top.right == prev) {
                stack.pop();
                list.add(top.val);
                prev = top;//证明当前元素已经被打印过了
            } else {
                cur = top.right;
            }
        }
        return list;
    }

    //获取树中节点的个数
    //思路；以前序遍历||中序遍历||后序遍历，会把每个节点都遍历到。遍历一个节点我们就计数一次

    int count = 0;
   public int size(TreeNode root){
        if(root == null) return 0;
        count++;
        size(root.left);
        size(root.right);
        return count;
    }
    //子问题思路：要算当前root的节点的个数 = 左子树节点的个数 + 右子树节点的个数 + 1
    public int size2(TreeNode root){
        if(root == null) return 0;
        return size2(root.left) + size2(root.right) + 1;
    }

    // 获取叶子节点的个数
    //思路：遍历
    int leafCount = 0;
    public int getLeafNodeCount(TreeNode root){
        if(root == null){
            return 0;
        }
       if(root.right == null && root.left == null){
           leafCount++;
       }else{
           getLeafNodeCount(root.left);
           getLeafNodeCount(root.right);
       }
         return leafCount;
    }
    // 子问题思路-求叶子结点个数
    //要求当前root有多少个叶子节点，相当于求root左树的叶子+右树的叶子
    public int getLeafNodeCount2(TreeNode root){
       if(root == null) return 0;
        //判定叶子节点
      if(root.left == null && root.right == null) {
          //是叶子节点就返回1
          return 1;
      }
        //返回左右叶子节点的个数
       return getLeafNodeCount2(root.left)+getLeafNodeCount2(root.right);
    }
    // 获取第K层节点的个数
    //root第k层节点的个数==root.left第k-1层 + root.right第k-1层
   public int getKLevelNodeCount(TreeNode root,int k){
        if(root == null) return 0;
        if(k == 1){
            return 1;
        }
        return getKLevelNodeCount(root.left,k-1)+getKLevelNodeCount(root.right, k-1);
    }
    // 获取二叉树的高度
    //左树和右树高度的最大值+1
    public int getHeight(TreeNode root){
       if(root == null) return  0;
       int leftHeight = getHeight(root.left);
       int rightHight = getHeight(root.right);
       return leftHeight > rightHight ?leftHeight + 1 : rightHight + 1;
    }
    // 检测值为value的元素是否存在
    //先序遍历，找到返回true
    public boolean find(TreeNode root, char val){
        if(root == null) return false;
        if(root.val == val){
            return true;
        }
        boolean leftFind = find(root.left,val);
        if(leftFind == true){
            return true;
        }
        boolean rightFind = find(root.right,val);
        if(rightFind == true){
            return true;
        }
        return false;
    }
    //层序遍历
    public void levelOrder(TreeNode root){
        //队列
       //先放左子树再放右子树
        if(root == null){
            return;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()){
            //ret会随着出栈元素的变化而变化
            TreeNode cur = queue.poll();
            System.out.print(cur.val + " ");
            if(cur.left != null){
                queue.offer(cur.left);
            }
            if (cur.right != null){
                queue.offer(cur.right);
            }
        }
    }
    public List<List<TreeNode>> levelOrder1(TreeNode root) {
        //队列
        //先放左子树再放右子树
        List<List<TreeNode>> ret = new ArrayList<>();
        if (root == null) {
            return ret;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            //ret会随着出栈元素的变化而变化
            //求一下当前队列的大小
            int size = queue.size();
            List<TreeNode> row = new ArrayList<>();
            //只有将当前行入链表完才会执行外部循环
            while (size != 0) {
                //也就是出队列4次    相当于把这层节点都出队了
                TreeNode cur = queue.poll();
                row.add(cur);
                size--;
                if(cur.left != null){
                    queue.offer(cur.left);
                }
                if (cur.right != null){
                    queue.offer(cur.right);
                }
            }
            //当前行已经处理完
            ret.add(row);
        }
    return ret;
    }
    // 判断一棵树是不是完全二叉树
    public boolean isCompleteTree(TreeNode root){
        if(root == null) return true;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()){
            TreeNode cur = queue.poll();
            //将全部元素包括null都放入栈中
            if(cur != null){
              queue.offer(cur.left);
              queue.offer(cur.right);
          }else{//证明遇到null
              break;
          }
        }
        while(!queue.isEmpty()){
            TreeNode cur = queue.poll();
            if(cur != null){
                return false;
            }
        }
        return true;
    }
    //翻转二叉树
    public TreeNode invertTree(TreeNode root) {
        //交换的是地址
        //每一颗子树都去交换左右孩子的指向  遍历二叉树的所有结点
        if(root == null) return null;
        TreeNode tmp = root.left;
        root.left = root.right;
        root.right = tmp;
        invertTree(root.left);
        invertTree(root.right);
        return root;
    }
    //判断是否是平衡二叉树
    public boolean isBalanced(TreeNode root) {
        //结论：只有每一棵子树都是高度平衡的才能说这棵树是高度平衡的
        //判断：高度差小于1 && 左树是平衡的（递归继续求高度）&& 右树也是平衡的（递归继续求高度）
        //最大问题：重复计算（效率低）->在判断父亲的同时判断子树平不平衡
        if(root == null){
            return true;
        }
        int leftHeight = getHeight(root.left);
        int rightHeight = getHeight(root.right);
        //Math.abs()    求绝对值
        return Math.abs(leftHeight - rightHeight) <= 1
                && isBalanced(root.left)
                && isBalanced(root.right);
    }
    //能否在求高度的时候就知道这棵树是否平衡
    //我拿着 你求得高度的值 去判断 当前高度<=1吗
    public int getHeight1(TreeNode root){
        if(root == null) return 0;
        int leftHeight = getHeight(root.left);
        int rightHeight = getHeight(root.right);
        if(leftHeight >= 0
                && rightHeight >=0
                && Math.abs(leftHeight-rightHeight) <= 1){
            return Math.max(leftHeight,rightHeight) + 1;
        }else{
            return -1;
        }
    }
    public boolean isBalanced1(TreeNode root) {
        if(root == null) return true;
        return getHeight1(root) >= 0;
    }
    //判断二叉树是否对称
    public boolean isSymmetric(TreeNode root) {
        if(root == null){
            return true;
        }
        return isSymmetricChild(root.left,root.right);
    }
    public boolean isSymmetricChild(TreeNode p,TreeNode q){
        if(p == null && q != null ||p != null && q == null ){
            return false;
        }
        if(p == null && q == null){
            return true;
        }
        if(p.val != q.val){
            return false;
        }
        return isSymmetricChild(p.left,q.right)
                && isSymmetricChild(p.right,q.left);
    }
    //创建一个字符二叉树（用户输入），并进行中序遍历
    public  void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextLine()) { // 注意 while 处理多个 case
            String str = in.nextLine();
            TreeNode root = creatTree(str);
            inorder(root);
        }
    }
    //注意：这里可能有多个对象，因此建议去掉static
    public int i = 0;
    //字符串是通过前序遍历遍历的
    public  TreeNode creatTree( String str){
        TreeNode root = null;

        if(str.charAt(i) != '#'){
            root = new TreeNode(str.charAt(i));
            i++;
            root.left = creatTree(str);
            root.right = creatTree(str);
        }else{
            i++;
        }
        //每次返回才串起来
        return root;
    }
    //中序遍历
    public static void inorder(TreeNode root){
        if(root == null){
            return;
        }
        inorder(root.left);
        System.out.print(root.val + " ");
        inorder(root.right);
    }
    //根据前序、中序遍历完成二叉树
    //因为递归的关系，可能导致右树遍历不到
    private int preIndex;
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        return buildTreeChild(preorder,inorder,0,inorder.length-1);
    }
    private TreeNode buildTreeChild(int[] preorder,int[] inorder,int inbegin,int inend){
        //1、没有左树    或者没有右树了
        if(inbegin > inend){
            return null;
        }
        //2、创建根节点
        TreeNode root = new TreeNode((char) preorder[preIndex]);
        //3、从中序遍历中找到根节点所在的下标
        int rootIndex = findIndex(inorder,inbegin,inend,preorder[preIndex]);
        if(rootIndex == -1){
            return null;
        }
        preIndex++;
        //root.left = ?
        //root.right = ?
        //创建左子树和右子树
        root.left = buildTreeChild(preorder,inorder,inbegin,rootIndex-1);
        root.right = buildTreeChild(preorder,inorder,rootIndex+1,inend);
        return root;
    }
    //找到当前前序遍历的根在中序遍历中的位置，返回它的下标
    private int findIndex(int[] inorder,int inbegin,int inend,int key){
        //注意这里的数组长度会改变的，i不能等于0
        for(int i = inbegin;i <= inend;i++){
            if(inorder[i] == key){
                return i;
            }
        }
        return -1;
    }
    //根据中序、后序完成一棵二叉树
    private int postIndex;
    public TreeNode buildTree1(int[] inorder, int[] postorder) {
        postIndex = postorder.length-1;
        return buildTreeChild1(postorder,inorder,0,inorder.length-1);
    }
    private TreeNode buildTreeChild1(int[] postorder,int[] inorder,int inbegin,int inend){
        //1、没有左树    或者没有右树了
        if(inbegin > inend){
            return null;
        }
        //2、创建根节点
        TreeNode root = new TreeNode((char) postorder[postIndex]);
        //3、从中序遍历中找到根节点所在的下标
        int rootIndex = findIndex(inorder,inbegin,inend,postorder[postIndex]);
        if(rootIndex == -1){
            return null;
        }
        postIndex--;
        //root.left = ?
        //root.right = ?
        //创建右子树和左子树

        root.right = buildTreeChild(postorder,inorder,rootIndex+1,inend);
        root.left = buildTreeChild(postorder,inorder,inbegin,rootIndex-1);
        return root;
    }
    //找到当前前序遍历的根在中序遍历中的位置，返回它的下标
    private int findIndex1(int[] inorder,int inbegin,int inend,int key){
        //注意这里的数组长度会改变的，i不能等于0
        for(int i = inbegin;i <= inend;i++){
            if(inorder[i] == key){
                return i;
            }
        }
        return -1;
    }
    public String tree2str(TreeNode root) {
        //1、左右两边都为空     返回
        //2、左边不为空
        //（
        //递归左边
        //）
        //3、左边为空但是右边不为空（）
        //情况
        //1、左边不为空：1、右边为空     2、右边不为空
        //2、左边为空：1、右边为空     2、右边不为空
        //3、右边空
        //4、右边不空
        StringBuilder stringBilder = new StringBuilder();
        tree2strChild(root,stringBilder);
        return stringBilder.toString();
    }
    private void tree2strChild(TreeNode t,StringBuilder stringBilder){
        if(t == null){
            return;
        }
        stringBilder.append(t.val);
        //左边不为空
        if(t.left != null){
            stringBilder.append("(");
            //递归左边
            tree2strChild(t.left,stringBilder);
            stringBilder.append(")");
        }else{
            if(t.right == null){
                return;
            }else{
                stringBilder.append("()");
            }
        }
        if(t.right != null){
            stringBilder.append("(");
            //递归右边
            tree2strChild(t.right,stringBilder);
            stringBilder.append(")");
        }else{
            return;
        }
    }
}

